package com.wxweven.algorithm.btree.postorder;

import com.wxweven.algorithm.btree.TreeNode;
import org.junit.Assert;
import org.junit.Test;

/**
 * 求二叉树的直径（即最远的任意两个节点之间的距离）
 * <p>
 * same method with 124,687 and 543
 */
public class LC543二叉树的直径 {

    int res = 0;

    public int diameterOfBinaryTree(TreeNode root) {
        if (root == null) {
            return 0;
        }

        helper(root);
        return res;
    }

    public int helper(TreeNode root) {
        if (root == null) {
            return 0;
        }

        int left = 0;
        if (root.left != null) {
            // 左节点存在的情况下，才 +1
            left = helper(root.left) + 1;
        }

        int right = 0;
        if (root.right != null) {
            // 右节点存在的情况下，才 +1
            right = helper(root.right) + 1;
        }

        // res 的值是 left + right
        res = Math.max(res, left + right);

        // 但是递归函数的返回值，只能选一边
        return Math.max(left, right);
    }

    @Test
    public void test() {
        TreeNode root = TreeNode.initTree();

        int longestPath = diameterOfBinaryTree(root);
        System.out.println(longestPath);

        Assert.assertEquals(5, longestPath);
    }
}
